#include<vector>
#include<algorithm>
using namespace std;

class Solution {
    bool isSatify(const vector<int>& weights, int load, int D) {
        int curLoad = load;
        for (int i = 0; i < weights.size(); ++i) {
            curLoad -= weights[i];
            if (curLoad < 0) {
                --D;
                if (D <= 0) return false;
                curLoad = load - weights[i];
            }
        }
        return true;

    }

public:
    int shipWithinDays(vector<int>& weights, int D) {
        int left = INT32_MIN, right = 0;
        for (int i = 0; i < weights.size(); ++i) {
            right += weights[i];
            left = max(left, weights[i]);
        }
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isSatify(weights, mid, D))
                right = mid - 1;
            else
                left = mid + 1;
        }
        return left;
    }
};